정규 언어

3. 예시

유한한 언어는 모두 정규 언어이다. 특히 {ε} = Ø^*도 정규 언어이다. 알파벳 {''a'', ''b''} 위의 정규 언어의 예로는 ''a''를 짝수 개 포함하는 모든 문자열의 집합이나, ''a'' 여러 개 뒤에 ''b'' 여러 개가 오는 꼴인 모든 문자열의 집합 따위가 있다.^[58]

정규 언어가 아닌 언어의 예로 { ''aⁿbⁿ'' | ''n'' ≥ 0 }이 있다.^[2] 유한 상태 기계의 기억력은 유한하기 때문에 ''a''가 몇 번 나왔는지 정확히 기억할 수 없으므로, 유한 상태 기계는 이 언어를 인지할 수 없다.

4. 동등한 형식화

형식언어 ''L''이 정규 언어라는 것은 다음과 동치이다.

• ''L''은 정규 표현식으로 나타낼 수 있다. (위의 정의)
• ''L''은 비결정적 유한 상태 기계가 인지하는 언어이다.^[59]
• ''L''은 결정적 유한 상태 기계가 인지하는 언어이다.^[59]
• ''L''은 정규 문법이 생성하는 언어이다.^[59]
• ''L''은 교대 유한 상태 기계가 인지하는 언어이다.
• ''L''은 양쪽 유한 상태 기계가 인지하는 언어이다.
• ''L''은 접두사 문법이 생성하는 언어이다.
• ''L''은 읽기 전용 튜링 기계가 인지하는 언어이다.
• ''L''은 일변수 2차 논리에서 정의할 수 있는 언어이다. (뷔히-엘고트-트라크텐브로트 정리)^[59]

5. 닫힘 성질

''K''와 ''L''이 정규 언어라면, 다음 연산의 결과도 정규 언어이다.

• 집합론적 부울 연산: 합집합 ''K'' ∪ ''L'', 교집합 ''K'' ∩ ''L'', 여집합 ''L''의 여집합, 상대 여집합 ''K'' - ''L''.^[22]
• 정규 연산: ''K'' ∪ ''L'', 문자열 연결 ''KL'', 클레이니 스타 ''L''^*.^[23]
• 트리오 연산: 문자열 준동형사상, 역 문자열 준동형사상, 그리고 정규 언어와의 교집합. 결과적으로, 임의의 유한 상태 변환에 대해 닫혀 있다. 예시로 정규 언어를 사용한 몫 ''K'' / ''L''가 있다. 더 나아가, 정규 언어는 '임의의' 언어를 사용한 몫에 대해 닫혀 있다. 즉, ''L''이 정규 언어라면, 임의의 ''K''에 대해 ''L'' / ''K''는 정규 언어이다.^[24]
• 역(또는 거울상) ''L''^R.^[25]

6. 결정 가능성

결정적 유한 상태 기계 A와 B가 주어졌을 때, 두 기계가 같은 언어를 인지하는지 결정할 수 있다.^[60] 따라서 위의 닫힘 성질을 이용하면 두 기계가 인지하는 정규 언어 ''L_A''와 ''L_B''에 대해 다음 문제를 결정할 수 있다.

• 포함: ''L''_''A'' ⊆ ''L''_''B''인가?^[61]
• 서로소: ''L''_''A'' ∩ ''L''_''B'' = Ø인가?
• 공집합: ''L''_''A'' = Ø인가?
• 전체집합: ''L''_''A'' = Σ^*인가?
• 소속: 주어진 ''a'' ∈ Σ^*에 대해, ''a'' ∈ ''L''_''A''인가?

7. 복잡도

계산 복잡도 이론에서 모든 정규 언어의 복잡도 종류는 때때로 '''REGULAR''' 또는 '''REG'''로 지칭되며, 이는 상수 공간(사용된 공간은 입력 크기와 독립적)에서 해결할 수 있는 결정 문제인 DSPACE(O(1))과 같다. '''REGULAR''' ≠ '''AC'''⁰인데, 이는 (자명하게) 입력의 1 비트 수가 짝수인지 홀수인지 결정하는 패리티 문제를 포함하고, 이 문제는 '''AC'''⁰에 속하지 않기 때문이다.^[35] 반면에, '''REGULAR'''는 '''AC'''⁰를 포함하지 않는데, 회문의 비정규 언어나 $\backslash \{0^n\; 1^n\; :\; n\; \backslash in\; \backslash mathbb\; N\backslash \}$와 같은 비정규 언어는 모두 '''AC'''⁰에서 인식될 수 있기 때문이다.^[36]

언어가 ''정규 언어''가 아니라면, 이를 인식하기 위해서는 최소한 Ω(log log ''n'')의 공간을 가진 기계가 필요하다(여기서 ''n''은 입력 크기).^[37] 다시 말해, DSPACE(o(log log ''n''))는 정규 언어의 종류와 같다. 실제로 대부분의 비정규 문제는 최소한 로그 공간을 사용하는 기계로 해결된다.

8. 촘스키 위계에서의 위치

모든 정규 언어는 문맥 자유 언어이다. 그러나 반대는 성립하지 않는다. { ''aⁿbⁿ'' | ''n'' ≥ 0 }는 문맥 자유 언어이지만 정규 언어가 아닌 예이다.

주어진 언어가 정규 언어인지 알아보려면 흔히 마이힐-네로드 정리나 펌핑 보조정리를 사용한다. 그 밖에 정규 언어의 닫힘 성질이나 콜모고로프 복잡도를 사용하는 방법도 있다.^[62]

• 유한 언어, 단어의 수가 유한한 언어.^[40] 이는 정규 언어이며, 언어의 모든 단어의 합집합인 정규 표현식을 만들 수 있다.
• 별-자유 언어, 빈 기호, 문자, 연결 및 모든 부울 연산자(집합 대수 참조)로 구성된 정규 표현식으로 설명할 수 있는 언어는 여집합을 포함하지만 클레이 스타는 포함하지 않는다. 이 클래스에는 모든 유한 언어가 포함된다.^[41]

9. 정규 언어의 하위 클래스

촘스키 위계에서 모든 정규 언어는 문맥 자유 언어임을 알 수 있다. 역은 성립하지 않는다. 예를 들어, ''a''의 개수와 ''b''의 개수가 같은 모든 문자열로 구성된 언어는 문맥 자유 언어이지만 정규 언어는 아니다. 언어가 정규 언어가 아님을 증명하기 위해 종종 마이힐-네로드 정리와 정규 언어 펌핑 보조정리를 사용한다. 다른 방법으로는 정규 언어의 폐쇄 속성^[38]을 사용하거나 콜모고로프 복잡도를 정량화하는 방법이 있다.^[39]

정규 언어의 중요한 하위 클래스는 다음과 같다.

• 유한 언어: 단어의 수가 유한한 언어.^[40] 이는 정규 언어이며, 언어의 모든 단어의 합집합인 정규 표현식을 만들 수 있다.
• 별-자유 언어: 빈 기호, 문자, 연결 및 모든 부울 연산자(집합 대수 참조)로 구성된 정규 표현식으로 설명할 수 있는 언어는 여집합을 포함하지만 클레이 스타는 포함하지 않는다. 이 클래스에는 모든 유한 언어가 포함된다.^[41]

10. 정규 언어의 단어 수

$s\_L(n)$을 $L$에서 길이가 $n$인 단어의 개수로 나타낸다. ''L''의 생성 함수는 다음과 같은 형식적 멱급수이다.

:$S\_L(z)\; =\; \backslash sum\_\{n\; \backslash ge\; 0\}\; s\_L(n)\; z^n\; \backslash \; .$

언어 ''L''의 생성 함수는 ''L''이 정규 언어일 경우 유리 함수이다.^[42] 따라서 모든 정규 언어 $L$에 대해, 수열 $s\_L(n)\_\{n\; \backslash geq\; 0\}$은 상수-재귀적이다. 즉, 정수 상수 $n\_0$, 복소수 상수 $\backslash lambda\_1,\backslash ,\backslash ldots,\backslash ,\backslash lambda\_k$와 복소수 다항식 $p\_1(x),\backslash ,\backslash ldots,\backslash ,p\_k(x)$가 존재하여 모든 $n\; \backslash geq\; n\_0$에 대해 $L$에서 길이가 $n$인 단어의 개수 $s\_L(n)$은 다음과 같다.

:$s\_L(n)=p\_1(n)\backslash lambda\_1^n+\backslash dotsb+p\_k(n)\backslash lambda\_k^n$.^{[43][44][45][46]}

따라서 특정 언어 $L\text{'}$의 비정규성은 $L\text{'}$에서 주어진 길이의 단어를 세어 증명할 수 있다. 예를 들어 균형 잡힌 괄호 문자열의 딕 언어를 고려해 보자. 딕 언어에서 길이가 $2n$인 단어의 개수는 카탈랑 수 $C\_n\backslash sim\backslash frac\{4^n\}\{n^\{3/2\}\backslash sqrt\{\backslash pi\}\}$와 같으며, 이는 $p(n)\backslash lambda^n$의 형태가 아니므로 딕 언어의 비정규성을 보여준다. 일부 고유값 $\backslash lambda\_i$가 같은 크기를 가질 수 있으므로 주의해야 한다. 예를 들어, 모든 짝수 이진 단어의 언어에서 길이가 $n$인 단어의 개수는 $p(n)\backslash lambda^n$의 형태가 아니지만, 짝수 또는 홀수 길이의 단어의 개수는 이 형태를 가지며, 해당 고유값은 $2,-2$이다. 일반적으로 모든 정규 언어에 대해 모든 $a$에 대해, 길이 $dm+a$인 단어의 개수가 점근적으로 $C\_a\; m^\{p\_a\}\; \backslash lambda\_a^m$이 되도록 하는 상수 $d$가 존재한다.^[47]

11. 일반화

정규 언어의 개념은 무한 단어(ω-오토마타)와 트리(트리 오토마타)로 일반화되었다.^[50][51]

유리 집합은 정규 언어의 개념을 반드시 자유일 필요는 없는 모노이드로 일반화한다.^[50][51]

유리 급수는 반환에 대한 형식적 멱급수의 맥락에서 일반화된다.^[52][53]

참조

_[1] 서적 Handbook of Formal Languages: Volume 1. Word, Language, Grammar Springer
_[2] 문서 Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
_[3] 문서 1. ⇒ 2. by [[Thompson's construction algorithm]]
_[4] 문서 2. ⇒ 1. by [[Kleene's algorithm]] or using [[Arden's lemma]]
_[5] 문서 2. ⇒ 3. by the [[powerset construction]]
_[6] 문서 3. ⇒ 2. since the [[deterministic finite automaton#Formal definition|former definition]] is stronger than the [[nondeterministic finite automaton#Formal definition|latter]]
_[7] 문서 2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
_[8] 문서 4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
_[9] 간행물 Chapter 12 - Decidability of S1S and S2S Springer 2002
_[10] 문서 3. ⇔ 10. by the [[Myhill–Nerode theorem]]
_[11] 문서 "''u''~''v'' is defined as: ''uw''∈''L'' if and only if ''vw''∈''L'' for all ''w''∈Σ^*"
_[12] 서적 see the proof in the ''[[Syntactic monoid#Syntactic equivalence|Syntactic monoid]]'' article, and see p.160 in Cambridge University Press
_[13] 서적 Algorithms https://books.google[...] Addison-Wesley Professional
_[14] 서적 Automatic Sequences: Theory, Applications, Generalizations https://books.google[...] Cambridge University Press
_[15] 서적 Finite Automata https://books.google[...] CRC Press
_[16] 서적 Discrete Mathematics and Its Applications 7th edition https://books.google[...] McGraw-Hill Science
_[17] 서적 Syntactic and Structural Pattern Recognition: Theory and Applications https://books.google[...] World Scientific 1990-01
_[18] 서적 The Oxford Handbook of Computational Linguistics https://books.google[...] Oxford University Press
_[19] 보고서 Representation of Events in Nerve Nets and Finite Automata http://www.rand.org/[...] 1951-12
_[20] 학술지 On Certain Formal Properties of Grammars http://www.sciencedi[...]
_[21] 문서 Chomsky 1959, Footnote 10, p.150
_[22] 문서 Salomaa (1981) p.28
_[23] 문서 Salomaa (1981) p.27
_[24] 학술대회 Constructivity in Computer Science, Summer Symposium, San Antonio, Texas, USA, June 19-22, Proceedings Springer
_[25] 문서 Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72
_[26] 문서 Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67
_[27] 문서 Check if ''L''_''A'' ∩ ''L''_''B'' = ''L''_''A''. Deciding this property is [[NP-hard]] in general; see [[:File:RegSubsetNP.pdf]] for an illustration of the proof idea.
_[28] 문서 Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401
_[29] 문서 Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
_[30] 문서 Hopcroft, Ullman (1979), Theorem 13.15, p.351
_[31] 서적 The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space https://people.csail[...] 13th Annual IEEE Symp. on Switching and Automata Theory 1972-10
_[32] 서적 Proc. 5th ann. symp. on Theory of computing (STOC) https://esp.mit.edu/[...] ACM
_[33] 문서 Hopcroft, Ullman (1979), Corollary p.353
_[34] 서적 Automata, Logics, and Infinite Games Springer 2002
_[35] 학술지 Parity, circuits, and the polynomial-time hierarchy
_[36] 서적 Logical foundations of proof complexity Association for Symbolic Logic
_[37] 간행물 Hierarchies of memory-limited computations Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design
_[38] 웹사이트 How to prove that a language is not regular? https://cs.stackexch[...] 2018-04-10
_[39] 서적 Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography https://www.worldcat[...] Springer 2004
_[40] 문서 A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
_[41] 서적 Logic and automata: history and perspectives Amsterdam University Press
_[42] 학술지 A necessary condition for the rationality of the zeta function of a regular language
_[43] 문서 Flajolet & Sedgweick, section V.3.1, equation (13).
_[44] 웹사이트 Number of words in the regular language $(00)^*$ https://cs.stackexch[...] 2018-04-10
_[45] 웹사이트 Proof of theorem for arbitrary DFAs https://cs.stackexch[...]
_[46] 웹사이트 Number of words of a given length in a regular language https://cs.stackexch[...] 2018-04-10
_[47] 문서 Flajolet & Sedgewick (2002) Theorem V.3
_[48] 학술지 Zeta functions of formal languages
_[49] 문서 Berstel & Reutenauer (2011) p.222
_[50] 서적 Automata, languages, and machines Academic Press
_[51] 서적 Finite automata, formal logic, and circuit complexity https://archive.org/[...] Birkhäuser
_[52] 문서 Berstel & Reutenauer (2011) p.47
_[53] 서적 Elements of automata theory Cambridge University Press
_[54] 문서 つまり[[正規演算]]に[[閉じている]]。
_[55] 서적 The Oxford Handbook of Computational Linguistics http://books.google.[...] Oxford University Press
_[56] 서적 Finite Automata http://books.google.[...] CRC Press
_[57] 서적 Handbook of Formal Languages: Volume 1. Word, Language, Grammar http://books.google.[...] Springer
_[58] 문서 Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
_[59] 문서 M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002.
_[60] 문서 Hopcroft, Ullman (1979), Theorem 3.8, p.64; Theorem 3.10, p.67도 참조.
_[61] 문서 L''{''A''} ∩ ''L''{''B''} = ''L''{''A''}인지 확인하면 된다.
_[62] 서적 Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography https://www.worldcat[...] Springer 2004